1. Field of the Invention
The present invention generally relates to the art of microelectronic integrated circuits, and more specifically to a method for estimating routability and congestion in a cell placement for a microelectronic integrated circuit.
2. Description of the Related Art
Microelectronic integrated circuits consist of a large number of electronic components that are fabricated by layering several different materials on a silicon base or wafer. The design of an integrated circuit transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in several layers.
The layout is then checked to ensure that it meets all of the design requirements. The result is a set of design files in a particular unambiguous representation known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator.
During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The component formation requires very exacting details about geometric patterns and separation between them. The process of converting the specifications of an electrical circuit into a layout is called the physical design. It is an extremely tedious and an error-prone process because of the tight tolerance requirements and the minuteness of the individual components.
Currently, the minimum geometric feature size of a component is on the order of 0.5 microns. However, it is expected that the feature size can be reduced to 0.1 micron within several years. This small feature size allows fabrication of as many as 4.5 million transistors or 1 million gates of logic on a 25 millimeter by 25 millimeter chip. This trend is expected to continue, with even smaller feature geometries and more circuit elements on an integrated circuit, and of course, larger die (or chip) sizes will allow far greater numbers of circuit elements.
Due to the large number of components and the exacting details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use Computer Aided Design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance.
The objective of physical design is to determine an optimal arrangement of devices in a plane or in a three dimensional space, and an efficient interconnection or routing scheme between the devices to obtain the desired functionality. Since space on a wafer is very expensive real estate, algorithms must use the space very efficiently to lower costs and improve yield.
Each microelectronic circuit device or cell includes a plurality of pins or terminals, each of which is connected to pins of other cells by a respective electrical interconnect wire network or net. A goal of the optimization process is to determine a cell placement such that all of the required interconnects can be made, and the total wirelength and interconnect congestion are minimized.
Prior art methods for achieving this goal comprise generating one or more initial placements, modifying the placements using optimization methodologies including genetic algorithm operators such as simulated evolution, or simulated annealing, and comparing the resulting placements using a cost criteria.
Multilayer-metal submicron ASIC technologies, which produce smaller die sizes and faster circuits, come with obvious cost and performance benefits. Submicron ASICs that accommodate more than 500K gates allow a user to put an entire system onto one chip.
On the other hand, the smaller geometries that make such densities possible also make timing-delay prediction and routing within die-size constraints much more difficult. While timing tools in both the logical and physical domains exist for such ASICS, the lack of accurate routability models and the failure to capture or predict unroutable designs have lead to costly design iterations.
Placement and routing are traditionally two separate and independent tasks. Although almost all placement methods attempt to minimize some combination of total wire length and net crossings, the routability of a placement, however, cannot be truly determined until all available routers have had their chances with the chip.
Discovering that a chip is unroutable at such a late design stage is highly costly and undesirable. This phenomenon is particularly noticeable when the netlist is generated using synthesis tools.